//
//  main.c
//  111. minDepth
//
//  Created by edz on 2020/7/13.
//  Copyright © 2020 edz. All rights reserved.
//

/*
 给定一个二叉树，找出其最小深度。
 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 说明: 叶子节点是指没有子节点的节点。
 
 示例:
 给定二叉树 [3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
 返回它的最小深度  2.
 */

#include <stdio.h>


// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};


int minDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    else if (!root->left && !root->right) {
        return 1;
    }
    else if (!root->left && root->right) {
        return minDepth(root->right)+1;
    }
    else if (root->left && !root->right) {
        return minDepth(root->left)+1;
    }
    else{
        int countleft = 1;
        int countright = 1;
        countleft += minDepth(root->left);
        countright += minDepth(root->right);
        return countleft < countright ? countleft : countright;
    }
    return 0;
}
